% -*- coding:utf-8 -*-

\documentclass{article}

\usepackage[utf8]{inputenc}
\usepackage[T1]{fontenc}
\usepackage[spanish]{babel}

\usepackage[bookmarks, hyperfootnotes=false, colorlinks=true,%
            urlcolor=blue, linkcolor=black,  citecolor=black,%
            pagecolor=black, anchorcolor=black, breaklinks=true]{hyperref}

\usepackage{enumerate}
\usepackage{eurosym}
\usepackage{graphicx}
\usepackage{times}
\usepackage{color}
\usepackage{array}
\usepackage{colortbl}
\usepackage{longtable}

\usepackage{fancyhdr}
\usepackage{fancybox}
\usepackage{listings}
\usepackage{subfigure}
\usepackage{hyperref}
\usepackage{tikz}

\usepackage{epsfig}
\usepackage{float}
\usepackage{amsmath}
\usepackage{lscape}

\setlength{\headheight}{16pt}
\setlength{\oddsidemargin}{17pt}
\setlength{\textwidth}{420pt}
\setlength{\topmargin}{0pt}
\setlength{\textheight}{600pt}
\setlength{\marginparwidth}{55pt}


\newcommand{\fsm}{\emph{FSM}}
\newcommand{\ice}{\emph{ICE}}
\newcommand{\icefield}{\emph{IceField}}
\newcommand{\slice}{\emph{Slice}}

\pagestyle{fancy}

\renewcommand{\footrulewidth}{0.5pt}

\fancyhead[R]{Práctica 1-Tarea 4}
\fancyhead[L]{Inteligencia Artificial}
\fancyfoot[R]{Manuel J. Abaldea Gª-Pliego}
\fancyfoot[L]{Búsqueda Heurística}


\newenvironment{float_code} {
      \begin{lst}
      }
      {
      \end{lst}
      }


\newfloat{lst}{H}{lop}[section]
\floatname{lst}{Listado}
\floatplacement{codigo}{!htb}
\floatstyle{plain}


\begin{document}

\begin{center}
\begin{Large}\textit{\textquotedblleft
Inteligencia Artificial \ \ Práctica 1
\textquotedblright}\end{Large}
\end{center}

\vspace*{0.5cm}

\begin{flushleft}
\begin{large}
\textit{
Alumno: Manuel J. Abaldea Gª-Pliego
}
\end{large}
\end{flushleft}

\vspace*{1cm}

\section*{Tarea 1: Tecnologías utilizadas y definición de estado y acción}
\subsection*{Tecnologías utilizadas y definición de estado y acción.}
\subsubsection*{Tecnologías usadas}
Para la realización de esta primera práctica utilizaré el lenguaje de
programación \emph{C++}.

\emph{C++} nos proporciona varias ventajas como
que es un lenguaje orientado a objetos, esto facilita la creación de
sistemas complejos proporcionando robustez y legibilidad en el
código. ¿Por qué no utilizar otro lenguaje orientado a objetos como
\emph{Java}? Por didáctica, he trabajado mucho menos con \emph{C++} y
quiero aprovechar este trabajo para practicar. Otra gran ventaja, que
se puede volver en mi contra, es el manejo de punteros y memoria; esto
nos proporciona un mejor control de la memoria y administración de los
recursos pero puede complicar el código si no se tiene suficiente
experiencia. También están las típicas ventajas de: es muy utilizado
y hay muchos tutoriales, existen muchas librerías, es compatible con
las de C, etc.

Para manipular las imágenes utilizaré una librería propia. Guardando
la imagen como \emph{PGM} en \emph{ASCI} puedo tomar la imagen como un
texto plano y trabajar con ella, de modo que una librería simple que
lea las cadenas de texto y obtenga la información necesaria para
trabajar es suficiente. Esto dará simplicidad a la práctica y bien
programada puede incluso ahorrar recursos.

\subsubsection*{Problema de espacio de estados simple.}
Para definir un estados utilizaremos:
\begin{itemize}
\item posición: en el eje X e Y
\end{itemize}

De modo que un estado sería: $\{X,Y\}$

Los actuadores serían los movimientos, considerando que comenzamos
desde la esquina superior izquierda:
\begin{itemize}
\item mover izquierda: X-1
\item mover derecha: X+1
\item mover abajo: Y+1
\item mover arriba: Y-1
\end{itemize}

\clearpage

El motivo de comenzar desde la esquina superior izquierda es que
utilizaré una matriz de enteros para representar el mapa, de modo que
de este modo las coordenadas X e Y coincidirán con las coordenadas de
la matriz, y el valor en dicha coordenada será el coste en escala de
grises (0-15) de la posición.
Antes de que los actuadores transformen el estado tendremos en cuenta:
\begin{itemize}
\item mover izquierda: solo si X-1 > 0
\item mover derecha: solo si X+1 < anchura del mapa
\item mover abajo: solo si Y+1 < profundidad del mapa
\item mover arriba: solo si Y-1 > 0
\end{itemize}

Multimap es un contenedor asociativo que contiene una lista ordenada de pares clave-valor. La clasificación se realiza de acuerdo con la Compare función de comparación, aplicada a las teclas. Las operaciones de búsqueda, inserción y eliminación tiene complejidad logarítmica .

El orden de los pares de clave y valor cuyas claves comparar equivalente es el orden de inserción y no cambia. (ya que C + +11)

std::multimap cumple los requisitos de Container,
AllocatorAwareContainer, AssociativeContainer y ReversibleContainer .

Para el almacenamiento de los nodos durante la ejecución utilizaré un
contenedor de datos asociativo \emph{multimap}  de \emph{C++}. Este
tipo de contenedor almacena pares clave-valor y los ordena
automáticamente por clave. Proporcionará la capacidad de acceso a los
nodos ya ordenados sin esfuerzo con una complejidad (según la
documentación) logarítmica).

\subsubsection*{Estructuras necesarias.}
Será necesario un árbol con los nodos de nuestro problema y una cola
con prioridad que será la frontera.
En nuestra implementación la cola con prioridad será el
\emph{multimap}. El orden de prioridad vendrá dado por la clave del
par valor-clave almacenado. Como clave indicaremos el valor por el
cual se ordenarán los nodos (profundidad o coste según el tipo de búsqueda).

Durante la ejecución del programa, en el proceso de búsqueda, la {\bf
  paginación en memoria} está pensada de modo que toda la frontera
esté almacenada en memoria primaria, para no saturarla se manejarán
todas las referencias a los datos mediante punteros realizando el
menor número de copias de datos posibles. Se optará por utilizar
\emph{SmartPointers} para que los datos borrados de la frontera y no
referenciados se limpien automáticamente.

\clearpage

\section*{Tarea 2: Test de la estructura de datos}
\subsection*{Estructura de datos para la cola con prioridad}
La estructura de datos para nuestra base de datos será la siguiente:
\begin{verbatim}
class Nodo{
  int CoX;
  int CoY;
  int cost;
  int prof;
  Nodo* father;
  float f;
 public:
  Nodo();
  ~Nodo();
  Nodo(int CoX_v, int CoY_v, int cost_v, int prof,
       Nodo* father_v, float f_v);
  int get_coX()const;
  int get_coY()const;
  int get_cost()const;
  int get_prof()const;
  Nodo* get_father()const;
  float get_f()const;
  void set_coX(int CoX_v);
  void set_coY(int CoY_v);
  void set_cost(int cost_v);
  void set_prof(int prof_v);
  void set_father(Nodo* father_v);
  void set_f(float f_v);
  void set(int CoX_v, int CoY_v, int prof_v, Nodo* father_v);
  void toString()const;
};
\end{verbatim}
Se almacenará el puntero a la estructura en un multimap, donde la
clave será el valor f:
\begin{verbatim}
  multimap<int,Nodo*> frontera;
  frontera.insert(pair<float,Nodo*>(nodo.get_f(), &nodo));
\end{verbatim}


\subsection*{Evaluar la capacidad de la estructura}
Para evaluar la estructura se ha utilizado el siguiente código:

\begin{verbatim}
int main(){
  clock_t ini, fin;
  int i;
  ini = clock();
  Nodo inicial(0,0,0,0,NULL,0);
  float(*p_func)(Nodo&, int*);
  multimap<int,Nodo*> frontera;
  for (i=0;i<Num_nodos;i++)
    frontera.insert(pair<float,Nodo*>(inicial.get_f(), &inicial+1));

  ini = clock() -ini;
  cout<< "Tiempo insercion: " << (((float)ini)/CLOCKS_PER_SEC) << endl;

  return 0;
}
\end{verbatim}
Y los resultados han sido los siguientes:
\begin{itemize}
\item 100000000 nodos en 244.06 segundos
\item Número de nodos hasta colapsar: CALCULAR
\item Tiempo medio de inserción de un nodo: 0,000002441 segundos.
\end{itemize}

\clearpage

\subsection*{Algoritmo de búsqueda de soluciones}
Se interpreta que el algoritmo devuelve un vector con los
identificadores de los nodos que componen la solución. Si existe un
único nodo con identificador 0 significará que no se ha encontrado
solución.

\begin{verbatim}
int* Busqueda (mapa_problema){
     frontera = Frontera(mapa_problema);   //nodo inicial
     while front.lenght > 0{
          nodo_actual = frontera.pop();    //extraer y eliminar nodo
          if nodo_actual.coordX = MAX_W and nodo_actual.coordY = MAX_D{
               sol_nodo = nodo_actual;
               break;
          }
          nodo_actual.expand(frontera);
     }
     if sol_nodo == NULL
          return 0;
     else
          return CrearSol(sol_nodo)
\end{verbatim}

\clearpage

\section*{Tarea 3: Construir función BÚSQUEDA}
Resultados:

 \begin{tabular}[!ht]{|c|c|c|c|} \hline
    \textbf{Algoritmo} & \textbf{Tamaño imagen} & \textbf{nodos
      expandidos} & \textbf{tiempo en hallar solución} \\ \hline
    Anchura & 500x500 & 250000 & 0.18 segundos  \\ \hline
    Anchura & 1000x1000 & 1000000 & 0.50 segundos  \\ \hline
    Coste Uniforme & 1000x1000 & 988871 & 0.62 segundos \\ \hline
    Coste Uniforme & 500x500 & 249911 & 0.15 segundos \\ \hline
    Profundidad & 1000x1000 & 3995 & 0.06 segundos \\ \hline
    Profundidad & 500x500 & 1995 & 0.01 segundos \\ \hline
    Prof. Acotada & 1000x1000 & 3995 & 0.06 segundos \\ \hline
    Prof. Acot. Iterativa & 1000x1000 & 10885 & 0.21 segundos  \\ \hline
  \end{tabular}

Para la profundidad acotada se ha tomado una cota de 2000, ya que con
cotas inferiores a 1998 no encontraba solución. Y para la profundidad
iterativa se han tenido encuenta estos datos para utilizar en la
prueba una profundidad de 1000, aumento de cota de 500 y 3 iteraciones.

\section*{Tarea 4: Búsqueda heurística}
Ya que teníamos definida la función de evaluación como un puntero a
función, para añadir estos algoritmos en el código implementado el
principal cambia a sido incluir las funciones en el \emph{switch} de
selección:
\begin{verbatim}
switch(estrategia){
  case 1: // anchura
    p_func = F_Anchura;
    break;
  case 2: // coste uniforme
    p_func = F_CosteU;
    break;
  case 3: // profundidad
    p_func = F_Prof;
    break;
  case 4: // A* Euclídea
    p_func = F_Euclidea;
    break;
  case 5: // A* Manhattan
    p_func = F_Manhattan;
    break;
  case 6: // profundidad acotada
    p_func = F_Prof;
    break;
  case 7: // profundidad iterativa
    p_func = F_Prof;
    break;
  default:
    cout << "Opcion incorrecta en P_FUNC!!!!" << endl;
    return false;
  }
\end{verbatim}

\clearpage

Y añadir las correspondientes funciones:

\begin{verbatim}
float F_Euclidea(Nodo &nodo_aux, int* posFin){
  float dist, cost;
  dist = sqrt(pow((posFin[0] - nodo_aux.get_coX()),2) +
	      pow((posFin[1] - nodo_aux.get_coY()),2));
  cost = nodo_aux.get_cost() + dist;
  return cost;
}
float F_Manhattan(Nodo &nodo_aux, int* posFin){
  float dist, cost;
  dist = abs(posFin[0] - nodo_aux.get_coX()) +
         abs(posFin[1] - nodo_aux.get_coY());
  cost = nodo_aux.get_cost() + dist;
  return cost;
}
\end{verbatim}

Los resultados han sido los siguientes:

 \begin{tabular}[!ht]{|c|c|c|c|c|} \hline
    \textbf{Algoritmo} & \textbf{Tamaño imagen} & \textbf{nodos
      expandidos} & \textbf{tiempo en hallar solución} & \textbf{coste}\\ \hline
    Coste Uniforme & 500x500 & 249911 & 0.35 segundos & 2484 \\ \hline
    Coste Uniforme & 1000x1000 & 988871 & 1.56 segundos & 7046 \\ \hline
    A* Euclídea & 500x500 & 262061 & 0.39 segundos & 2484 \\ \hline
    A* Euclídea & 1000x1000 & 1005172 & 1.72 segundos & 7046 \\ \hline
    A* Manhattan & 500x500 & 272232 & 0.40 segundos &  2484 \\ \hline
    A* Manhattan & 1000x1000 & 10053698 & 1.74 segundos &  7046 \\ \hline
  \end{tabular}

Destacar que, aunque los algoritmos \emph{A*} despliegan menos nodos
que el de \emph{Coste Uniforme} tardan más tiempo en encontrar el nodo
solución. Se achaca este tiempo al cómputo extra de cálculo.

\clearpage

Los algoritmos \emph{A*} obtienen la misma solución, pero esta
solución difiere de la obtenida con costo uniforme.

\begin{figure}[!h]
  \center
  \includegraphics[scale=0.4]{CO_image_out.png}
  \caption{Mapa 1000x1000. Solución con COSTO UNIFORME}
\end{figure}
\begin{figure}[!h]
  \center
  \includegraphics[scale=0.4]{A_image_out.png}
  \caption{Mapa 1000x1000. Solución con A*}
\end{figure}

\clearpage
\section*{Código implementado}
El código, así como el seguimiento de esta práctica está disponible en:

\url{https://code.google.com/p/ia-2012-13/}

\end{document}
